\chapter{常见算法}
\section{Kahan 求和算法}
Kahan 求和算法（Kahan summation algorithm），有时也称为补偿求和算法（compensated summation algorithm），是一种数值分析中用于最小化在进行浮点数加法运算时累积的舍入误差的技术。尤其在对大量数值进行求和时，标准的累加方法由于浮点数的精度有限，可能会导致显著的精度损失。

为什么需要 Kahan 求和？

浮点数在计算机中以有限的精度表示。当两个大小相差很大的浮点数相加时，较小的数可能会因为尾数对齐而丢失其低位有效数字，导致精度损失。如果重复进行这样的加法（例如，对一个包含许多小数值的数组求和），这些微小的误差会逐渐累积，最终导致结果与真实值之间存在较大的偏差。

Kahan 求和算法的原理：

Kahan 求和算法的核心思想是跟踪并补偿在每次加法中丢失的精度。它通过维护一个额外的变量（通常称为 c 或 compensation）来记录这些丢失的低位。

算法的步骤大致如下：
\begin{itemize}
	\item 初始化一个累加器 sum 为 0.0，以及一个补偿变量 c 为 0.0。
	\item 对于输入中的每个数值 x：
\begin{enumerate}
\item  计算一个临时和 y = x + c。这里的 c 是上一轮加法中丢失的精度。
\item  计算一个新的临时和 t = sum + y。
\item  计算本次加法中丢失的精度 c = (t - sum) - y。这个步骤利用了浮点运算的特性来估计丢失的低位。
\item  将新的临时和 t 赋值给累加器 sum。
\end{enumerate}
\end{itemize}
最终的求和结果是 sum。

详细解释步骤 c：c = (t - sum) - y

这一步是 Kahan 求和算法的关键。让我们分解一下：
\begin{itemize}
\item t = sum + y = sum + (x + c) 是当前的近似和。
\item (t - sum) 理想情况下应该等于 y (即 x + c)。然而，由于浮点运算的舍入误差，这个值可能略有不同。
\item (t - sum) - y 计算了 t 中由于与 sum 相加而引入的误差，并减去 y 本身，从而得到在 y (包含了上一轮的补偿 c) 与 sum 相加时真正丢失的精度。这个丢失的精度被存储回 c，以便在下一次迭代中进行补偿。
\end{itemize}
